The invention relates to routing packets in a computer network.
A computer network enables devices such as processors, mass storage devices, and printers to communicate with each other over communication links. Each device is connected to a node which interfaces the device to the network, allowing it to transfer data to and from other network nodes. The nodes are interconnected by the communication links in any of a variety of configurations and may contain any number of nodes.
The nodes at both ends of a particular communication link are commonly referred to as neighboring nodes. To send information to a non-neighboring node, a node transmits the information over the communication link connected to a neighboring node. The information is then forwarded from neighbor to neighbor until it reaches its destination.
Data and control messages are typically transmitted over the network in the form of packets. The packets contain, in addition to the data or control messages, network specific information, such as the identity of the source node which prepares the packet and launches it on to the network. This identity information is contained in a first section of the packet referred to as a header, which precedes the data or control message.
Packets may be transmitted from a given source node to a given destination node either by broadcasting the packet over the entire network or by routing the packet along a specific group of nodes connecting the source to the destination. Broadcasting consists of sending a packet to every node on the network.
One method of broadcasting packets over the network is called flooding. Flooding requires each node which receives a packet to transmit it to each of its neighboring nodes, except the node from which it was received. Copies of the packet eventually travel throughout the network to every node over every communication link. Typically multiple copies of the packet reach every node.
Alternatively, a packet may be sent to a destination node via a single route. Typically the source node launches a packet to a destination node by providing a neighbor node with the packet and with information regarding its destination. The neighbor, and each subsequent node which receives the packet, makes an independent decision as to the next node to which the packet should be forwarded in order to reach the destination specified by the source.
Such routing (called path specific routing) is less costly than flooding because it avoids redundant transmissions; but if a single node along the specified path fails to forward the packet, the destination node will not receive it. In flooding, conversely, individual node failures will not prevent delivery of a packet as long as a complete functioning path connects the source and destination.
Path specific routing operates reliably only if a reliable model of the network topology is maintained. This may be provided manually by a system operator updating the network model each time a node is added to and removed from the network.
A packet traveling over a network may be lost or corrupted by improperly operating nodes (i.e., nodes with faulty hardware or software) and by network misconfigurations.
Improperly operating nodes may delay packets, sporadically lose packets, alter packets, and fail to transmit packets to or from a particular node, thus disrupting the delivery of one or more specific packets. An improperly operating node may also generate such a high volume of traffic, for example, by transmitting packets at a rate which is faster than the network nodes can process, so as to congest the entire network. Node failures in which the node continues to operate, but in a faulty manner, are generally called byzantine failures.
Nodes may operate "maliciously" as a result of, for example, network sabotage. A malicious node may delay, alter and/or fail to transmit selected packets while properly transmitting others. Further it may purposefully transmit inaccurate or conflicting information in a form which appears correct.